package leetcode_2401_2500;

import java.util.TreeSet;

public class LeeCode_2498_slow {
    public static void main(String[] args) {
        System.out.println(maxJump(new int[]{0, 3, 9}));
        System.out.println(maxJump(new int[]{0,2,5,6,7}));
    }
    private static int maxJump(int[] stones) {
        int n = stones.length;
        TreeSet<Integer> set = new TreeSet<>();
        for (int stone : stones) {
            set.add(stone);
        }
        int l = 0, r = stones[n - 1];
        while (l < r){
            int m = (l + r) / 2;
            if (check(set, stones, m)){
                r = m;
            }else {
                l = m + 1;
            }
        }
        return l;
    }
    private static boolean check(TreeSet<Integer> set, int[] stones, int d){
        TreeSet<Integer> copy = new TreeSet<>(set);
        int max = stones[stones.length - 1];
        return  go(copy, 0, max, d) && back(copy, max, 0, d);
    }
    private static boolean go(TreeSet<Integer> set, int now, int goal, int d){
        Integer nk = set.lower(now + d + 1);
        if (nk == now)
            return false;
        if (now != 0)
            set.remove(now);
        if (nk == goal)
            return true;
        return go(set, nk, goal, d);
    }
    private static boolean back(TreeSet<Integer> set, int now, int goal, int d){
        Integer nk = set.higher(now - d - 1);
        if (nk == goal)
            return true;
        if (nk == now)
            return false;
        return back(set, nk, goal, d);
    }
}
